// greedy alg.
// 通过局部最优解得到全局最优解
// 正向贪心：始终维护最远可达位置
// max = i + nums[i], [i, max]计算max(i+nums[i])，直到最后位置
// time:O(n), space: O(1)
func jump(nums []int) int {
	n := len(nums)
	end := 0
	maxPos := 0
	steps := 0
	for i := 0; i < n-1; i++ {
		if i+nums[i] > maxPos {
			maxPos = i + nums[i]
		}
		if i == end {
			end = maxPos
			steps++
		}
	}
	return steps
}